package org.algorithm.express;

import java.util.Arrays;

public class MinPath {

    // 表示已经加入生成树的顶点数组
    private boolean[] visited;

    // 记录着生成树到达图中剩余顶点的权值数组
    private int[] weight;

    private int[] parent;

    private Graph graph;

    public MinPath(Graph graph) {
        this.visited = new boolean[graph.vCount];
        this.graph = graph;
        initWeight();
        initParent();
    }

    private void initWeight() {
        weight = new int[graph.vCount];
        Arrays.fill(weight, Integer.MAX_VALUE);
    }

    private void initParent() {
        parent = new int[graph.vCount];
        Arrays.fill(parent, -1);
    }

    // prim 获取最短路径
    public int[] getMinPath() {
        // 默认从第零个顶点开始开始
        weight[0] = 0;
        parent[0] = -1;
        for (int i = 0; i < graph.vCount - 1; i++) {
            int minIndex = minKey();
            visited[minIndex] = true;
            // Visited数组加入了新的成员，所以要更新权值数组
            for (int v = 0; v < graph.vCount; v++) {
                // 权值不为0，且不在生成树中，并且小于已有的权值
                if (graph.graph[minIndex][v] != 0 && !visited[v] && graph.graph[minIndex][v] < weight[v]) {
                    parent[v] = minIndex;
                    weight[v] = graph.graph[minIndex][v];
                }
            }
        }

        print_MST();
        return new int[]{};
    }

    public void print_MST() {
        int minCost = 0;
        System.out.println("最小生成树为：");
        //遍历 parent 数组
        for (int i = 1; i < graph.vCount; i++) {
            //parent 数组下标值表示各个顶点，各个下标对应的值为该顶点的父节点
            System.out.println((parent[i]) + " - " + (i) + " wight:" + graph.graph[i][parent[i]]);//由于数组下标从 0 开始，因此输出时各自 +1
            //统计最小生成树的总权值
            minCost += graph.graph[i][parent[i]];
        }

        System.out.print("总权值为：" + minCost);
    }

    // 找出最小权值顶点
    private int minKey() {
        int min = Integer.MAX_VALUE;
        int minIndex = 0;
        for (int i = 0; i < weight.length; i++) {
            // 当前顶点不在生成树里，且权值小于min
            if (!visited[i] && weight[i] < min) {
                min = weight[i];
                minIndex = i;
            }
        }

        return minIndex;
    }


}
